/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年04月29日
*   描    述：
*
================================================================*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
  int key;
  void *value;
  struct Node *next;
} Node;

typedef struct Map {
  Node **buckets;
  int size;
} Map;

// 创建一个新的节点
Node *createNode(int key, void *value) {
  Node *node = (Node *)malloc(sizeof(Node));
  if (node == NULL) {
    perror("Error: unable to allocate memory for new node.");
    exit(EXIT_FAILURE);
  }
  node->key = key;
  node->value = value;
  node->next = NULL;
  return node;
}

// 删除一个节点
void deleteNode(Node *node) { free(node); }

// 计算哈希值
int hash(int key, int size) {
  int hash = 0;
  hash = 31 * hash + key;
  return abs(hash % size);
}

// 创建一个新的 Map
Map *CreateMap(int size) {
  Map *map = (Map *)malloc(sizeof(Map));
  if (map == NULL) {
    perror("Error: unable to allocate memory for new map.");
    exit(EXIT_FAILURE);
  }
  map->size = size;
  map->buckets = (Node **)calloc(size, sizeof(Node *));
  if (map->buckets == NULL) {
    perror("Error: unable to allocate memory for buckets.");
    exit(EXIT_FAILURE);
  }
  return map;
}

// 删除一个 Map
void DeleteMap(Map *map) {
  int i = 0;
  for (; i < map->size; ++i) {
    Node *node = map->buckets[i];
    while (node != NULL) {
      Node *tmp = node;
      node = node->next;
      deleteNode(tmp);
    }
  }
  free(map->buckets);
  free(map);
}

// 添加键值对
void Put(Map *map, int key, void *value) {
  int idx = hash(key, map->size);
  Node *node = map->buckets[idx];
  while (node != NULL) {
    if (node->key == key) {
      node->value = value;
      return;
    }
    node = node->next;
  }
  node = createNode(key, value);
  node->next = map->buckets[idx];
  map->buckets[idx] = node;
}

// 获取键对应的值，如果不存在则返回 NULL
void *Get(Map *map, int key) {
  int idx = hash(key, map->size);
  Node *node = map->buckets[idx];
  while (node != NULL) {
    if (node->key == key) return node->value;
    node = node->next;
  }
  return NULL;
}

typedef struct LRUListNode {
  int key;
  int val;
  struct LRUListNode *next;
  struct LRUListNode *pre;
} LRUListNode;

typedef struct LRUCache {
  LRUListNode *hot;   // 最热的数据节点
  LRUListNode *cold;  // 最冷的数据节点
  void *buffer;       // 整个LRU使用的buffer，一次性分配与释放
  int capacity;       // LRU容量
  Map *key2Nodemap;   // map<key,ListNode*>
} LRUCache;

//  以 正整数 作为容量 capacity 初始化 LRU 缓存
LRUCache *lRUCacheCreate(int capacity) {
  // 生成LRUCache对象，LRUCache的容量为capacity，hot指向双向链表的头，cold指向双向链表的尾部。
  LRUCache *lRUCache = (LRUCache *)malloc(sizeof(LRUCache));
  memset(lRUCache, 0, sizeof(LRUCache));

  lRUCache->capacity = capacity;
  lRUCache->key2Nodemap = CreateMap(3000 * 4);
  lRUCache->buffer = malloc(sizeof(LRUListNode) * lRUCache->capacity);

  LRUListNode *listNodes = (LRUListNode *)lRUCache->buffer;
  memset(listNodes, 0, sizeof(LRUListNode) * lRUCache->capacity);
  lRUCache->hot = listNodes;
  lRUCache->cold = listNodes + lRUCache->capacity - 1;
  for (int i = 0; i < lRUCache->capacity - 1; i++) {
    listNodes[i].key = -1;
    listNodes[i].next = listNodes + i + 1;
    listNodes[i + 1].pre = listNodes + i;
  }
  lRUCache->cold->key = -1;
  return lRUCache;
}

// 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
int lRUCacheGet(LRUCache *obj, int key) {
  // 查看key2Nodemap是否存在当前key，不存在返回-1。
  void *value = Get(obj->key2Nodemap, key);
  if (value == NULL) {
    return -1;
  }

  LRUListNode *currNode = (LRUListNode *)value;

  // 如果当前key是hot指向的node
  if (currNode->key == obj->hot->key) {
    return obj->hot->val;
  }
  // 如果当前key是cold指向的node
  if (currNode == obj->cold) {
    obj->cold = obj->cold->pre;
    obj->cold->next = NULL;
    currNode->next = obj->hot;
    obj->hot->pre = currNode;
    obj->hot = currNode;
    obj->hot->pre = NULL;
    if (obj->capacity == 2) {
      obj->cold->pre = obj->hot;
    }
    return obj->hot->val;
  }

  // 处理其余中间节点
  currNode->next->pre = currNode->pre;
  currNode->pre->next = currNode->next;
  currNode->next = obj->hot;
  obj->hot->pre = currNode;
  obj->hot = currNode;
  obj->hot->pre = NULL;

  return currNode->val;
}

/*
 * 如果关键字 key 已经存在，则变更其数据值 value ；
 * 如果不存在，则向缓存中插入该组 key-value 。
 * 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 */
void lRUCachePut(LRUCache *obj, int key, int value) {
  // 先调用lRUCacheGet函数，如果key存在则当前key所在的节点已经被更新到hot端，则直接更新更新hot端的value即可。
  int _value = lRUCacheGet(obj, key);
  if (_value != -1) {
    obj->hot->val = value;
    return;
  }
  if (obj->cold->key != -1) {
    Put(obj->key2Nodemap, obj->cold->key, NULL);
  }
  // 当前key不存在与队列时，将cold端的节点值更新成入参key和value，并将当前节点挂到hot端。
  obj->cold->key = key;
  obj->cold->val = value;
  obj->cold->next = obj->hot;
  obj->hot->pre = obj->cold;
  obj->hot = obj->cold;
  obj->cold = obj->cold->pre;
  obj->hot->pre = NULL;
  obj->cold->next = NULL;

  // 更新key2Nodemap
  Put(obj->key2Nodemap, key, obj->hot);
}

void lRUCacheFree(LRUCache *obj) {
  if (obj != NULL) {
    if (obj->key2Nodemap != NULL) {
      DeleteMap(obj->key2Nodemap);
    }
    if (obj->buffer != NULL) {
      free(obj->buffer);
    }
  }
}

int main() {
  // 创建 LRUCache 对象
  int capacity = 3;
  LRUCache *lRUCache = lRUCacheCreate(capacity);

  // 测试用例
  lRUCachePut(lRUCache, 11, 4);
  lRUCachePut(lRUCache, 12, 24);
  lRUCachePut(lRUCache, 5, 18);
  lRUCachePut(lRUCache, 13, 4);
  lRUCachePut(lRUCache, 7, 23);
  lRUCachePut(lRUCache, 12, 27);
  lRUCachePut(lRUCache, 13, 2);
  lRUCachePut(lRUCache, 1, 27);
  lRUCachePut(lRUCache, 6, 24);

  // 释放 LRUCache 对象
  lRUCacheFree(lRUCache);

  return 0;
}

// int main() {
//   // 创建 LRUCache 对象
//   int capacity = 3;
//   LRUCache *lRUCache = lRUCacheCreate(capacity);

//   // 调用 lRUCachePut 添加键值对
//   lRUCachePut(lRUCache, 1, 1);
//   lRUCachePut(lRUCache, 2, 2);
//   lRUCachePut(lRUCache, 3, 3);
//   lRUCachePut(lRUCache, 4, 4);

//   // 调用 lRUCacheGet 获取值
//   int param = lRUCacheGet(lRUCache, 4);
//   printf("%d\n", param);  // 输出: 4
//   param = lRUCacheGet(lRUCache, 3);
//   printf("%d\n", param);  // 输出: 3
//   param = lRUCacheGet(lRUCache, 2);
//   printf("%d\n", param);  // 输出: 2
//   param = lRUCacheGet(lRUCache, 1);
//   printf("%d\n", param);  // 输出: 1

//   // 调用 lRUCachePut 添加键值对
//   lRUCachePut(lRUCache, 5, 5);

//   // 调用 lRUCacheGet 获取值
//   param = lRUCacheGet(lRUCache, 1);
//   printf("%d\n", param);  // 输出: 1
//   param = lRUCacheGet(lRUCache, 2);
//   printf("%d\n", param);  // 输出: 2
//   param = lRUCacheGet(lRUCache, 3);
//   printf("%d\n", param);  // 输出: 3
//   param = lRUCacheGet(lRUCache, 4);
//   printf("%d\n", param);  // 输出: 4
//   param = lRUCacheGet(lRUCache, 5);
//   printf("%d\n", param);  // 输出: 5

//   // 释放 LRUCache 对象
//   lRUCacheFree(lRUCache);

//   return 0;
// }

// int main() {
//   // 创建 LRUCache 对象
//   int capacity = 1;
//   LRUCache *lRUCache = lRUCacheCreate(capacity);

//   // 调用 lRUCachePut 添加键值对
//   lRUCachePut(lRUCache, 2, 1);

//   // 调用 lRUCacheGet 获取值
//   int param_1 = lRUCacheGet(lRUCache, 2);
//   printf("%d\n", param_1);  // 输出: 2

//   // 释放 LRUCache 对象
//   lRUCacheFree(lRUCache);

//   return 0;
// }

// int main() {
//   // 创建 LRUCache 对象
//   int capacity = 2;
//   LRUCache *lRUCache = lRUCacheCreate(capacity);

//   // 调用 lRUCachePut 添加键值对
//   lRUCachePut(lRUCache, 1, 1);
//   lRUCachePut(lRUCache, 2, 2);

//   // 调用 lRUCacheGet 获取值
//   int param_1 = lRUCacheGet(lRUCache, 1);
//   printf("%d\n", param_1);  // 输出: 1

//   // 调用 lRUCachePut 添加键值对
//   lRUCachePut(lRUCache, 3, 3);

//   // 调用 lRUCacheGet 获取值
//   int param_2 = lRUCacheGet(lRUCache, 2);
//   printf("%d\n", param_2);  // 输出: -1

//   // 调用 lRUCachePut 添加键值对
//   lRUCachePut(lRUCache, 4, 4);

//   // 调用 lRUCacheGet 获取值
//   int param_3 = lRUCacheGet(lRUCache, 1);
//   printf("%d\n", param_3);  // 输出: -1

//   // 调用 lRUCacheGet 获取值
//   int param_4 = lRUCacheGet(lRUCache, 3);
//   printf("%d\n", param_4);  // 输出: 3

//   // 调用 lRUCacheGet 获取值
//   int param_5 = lRUCacheGet(lRUCache, 4);
//   printf("%d\n", param_5);  // 输出: 4

//   // 释放 LRUCache 对象
//   lRUCacheFree(lRUCache);

//   return 0;
// }